package com.clstu.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 演示二分查找(要求数组有序),----(进阶版)--->(如果该值有很多个对应的数)可以返回多个下标
 */
public class BinarySearch {
    public static int count = 0;
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=i+1;
        }
        System.out.println(binarySearch2(arr,0,arr.length-1,55));
    }

    //编写方法实现二分查找
    public static int binarySearch(int[] arr, int left,int right ,int findVal){
        //思路分析,直接跟中间的数比较,如果>findVal,就像右边递归查找
        //                       如果<findVal,就像右边递归查找
        //                       如果=findVal,直接返回
        //先判断是否需要查找(left>right,说明找不到,直接返回-1)
        if(left>right){
            return -1;
        }
        int mid = (right+left)/2;
        //如果大于
        if(findVal>arr[mid]){
            return binarySearch(arr,mid+1,right,findVal);
        }
        //如果小于
        if(findVal<arr[mid]){
            return binarySearch(arr,left,mid-1,findVal);
        }
        //如果等于
        return mid;
    }

    //编写方法实现二分查找升级版,可以返回多个相同数的下标,保存再ArrayList中返回
    public static List<Integer> binarySearch2(int[] arr, int left,int right ,int findVal){
        System.out.println("二分查找次数:"+(++count));
        if(left>right){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> resList = new ArrayList<>();
        int mid = (right+left)/2;
        if (findVal>arr[mid]){
            return binarySearch2(arr,mid+1,right,findVal);
        }
        if (findVal<arr[mid]){
            return binarySearch2(arr,left,mid-1,findVal);
        }
        //如果找到,先加入mid的下标
        resList.add(mid);
        //向做扫描,
        for (int i = mid-1; i>=left && arr[i]==findVal; i--) {
            resList.add(i);
        }
        //向右扫描
        for (int i = mid+1; i<=right && arr[i]==findVal;i++){
            resList.add(i);
        }
        return resList;
    }
}
